//使用最小花费爬楼梯
//测试链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
public class MinCostClimbingStairs {
    //方法一：从左向右填表
    public int minCostClimbingStairs1(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        for(int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }

    //从右向左填表
    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        dp[n-1] = cost[n-1]; dp[n-2] = cost[n-2];

        for(int i = n-3; i >= 0; i--) {
            //从dp[i+1]位置出发或者dp[i+2]位置出发的最小花费
            dp[i] = Math.min(dp[i+1], dp[i+2]) + cost[i];
        }

        return Math.min(dp[0], dp[1]);
    }
}
